package com.cb2.algorithm.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * <a href='https://leetcode.cn/problems/intersection-of-two-linked-lists/'>相交链表(Intersection of Two Linked Lists)</a>
 * <p>给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。</p>
 * <p>题目数据 保证 整个链式结构中不存在环。</p>
 * <p>注意，函数返回结果后，链表必须 保持其原始结构 。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *     <a href='https://leetcode.cn/problems/intersection-of-two-linked-lists/'>示例</a>
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>listA 中节点数目为 m</li>
 *         <li>listB 中节点数目为 n</li>
 *         <li>1 <= m, n <= 3 * 10^4</li>
 *         <li>1 <= Node.val <= 10^5</li>
 *         <li>0 <= skipA <= m</li>
 *         <li>0 <= skipB <= n</li>
 *         <li>如果 listA 和 listB 没有交点，intersectVal 为 0</li>
 *         <li>如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]</li>
 *     </ul>
 * </p>
 * <b>进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？</b>
 *
 * @author c2b
 * @since 2023/10/31 14:26
 */
public class LC0160IntersectionOfTwoLinkedLists_S {

    public static class Solution {
        public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
            // 分别计算两个链表的长度，计算出差值，较长的链表先走差值步
            ListNode tempNode;
            int diffLen = 0;
            tempNode = headA;
            while (tempNode != null) {
                ++diffLen;
                tempNode = tempNode.next;
            }
            tempNode = headB;
            while (tempNode != null) {
                --diffLen;
                tempNode = tempNode.next;
            }
            // 如果 diffLen > 0，说明A链表长;如果 diffLen < 0，说明B链表长
            ListNode longerList = diffLen > 0 ? headA : headB;
            ListNode shorterList = longerList != headA ? headA : headB;
            // 较长链表先走差值步
            for (int i = Math.abs(diffLen); i > 0 && longerList != null; --i) {
                longerList = longerList.next;
            }
            // 两条链表一起动。此时两条链表一样长，shorterList 不会出现空指针
            while (longerList != null && shorterList != null && longerList != shorterList) {
                longerList = longerList.next;
                shorterList = shorterList.next;
            }
            return longerList;
        }


        public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) {
                return null;
            }
            ListNode p = headA;
            ListNode q = headB;
            while (p != q) {
                p = p == null ? headB : p.next;
                q = q == null ? headA : q.next;
            }
            return p;
        }

        /**
         * 使用Hash表
         */
        public ListNode getIntersectionNode3(ListNode headA, ListNode headB) {
            Set<ListNode> visited = new HashSet<>();
            ListNode temp = headA;
            while (temp != null) {
                visited.add(temp);
                temp = temp.next;
            }
            temp = headB;
            while (temp != null) {
                if (visited.contains(temp)) {
                    return temp;
                }
                temp = temp.next;
            }
            return null;
        }
    }

    public static void main(String[] args) {
        ListNode node8 = new ListNode(8);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node8.next = node4;
        node4.next = node5;

        ListNode node4_1 = new ListNode(4);
        ListNode node1_1 = new ListNode(1);
        node4_1.next = node1_1;
        node1_1.next = node8;

        ListNode node5_2 = new ListNode(5);
        ListNode node6_2 = new ListNode(6);
        ListNode node1_2 = new ListNode(1);
        node5_2.next = node6_2;
        node6_2.next = node1_2;
        node1_2.next = node8;

        Solution solution = new Solution();
        Printer.printListNode(solution.getIntersectionNode1(node4_1, node5_2));
        Printer.printListNode(solution.getIntersectionNode2(node4_1, node5_2));
        Printer.printListNode(solution.getIntersectionNode3(node4_1, node5_2));
    }
}